
https://leetcode.cn/problems/smallest-k-lcci/description/
//class Solution {
//public:
//    vector<int> smallestK(vector<int>& nums, int k) {
//        srand(time(nullptr));
//        qsort(nums, 0, nums.size() - 1);
//        return { nums.begin(),nums.begin() + k };
//    }
//
//    void qsort(vector<int>& nums, int l, int r) {
//        if (l >= r) {
//            return;
//        }
//
//        int left = l - 1, right = r + 1, i = l;
//        int key = Get(nums, l, r);
//        while (i < right) {
//            if (nums[i] < key) {
//                swap(nums[i++], nums[++left]);
//            }
//            else if (nums[i] > key) {
//                swap(nums[i], nums[--right]);
//            }
//            else {
//                i++;
//            }
//        }
//        qsort(nums, l, left);
//        qsort(nums, right, r);
//    }
//
//    int Get(vector<int>& nums, int l, int r) {
//        int x = rand();
//        return nums[x % (r - l + 1) + l];
//    }
//};


https://leetcode.cn/problems/xx4gT2/description/
//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        srand(time(nullptr));
//        return qsort(nums, 0, nums.size() - 1, k);
//    }
//
//    int qsort(vector<int>& nums, int l, int r, int k) {
//
//        if (l == r) {
//            return nums[l];
//        }
//        int left = l - 1;
//        int right = r + 1;
//        int i = l;
//        int key = Grand(nums, l, r);
//        while (i < right) {
//            if (key > nums[i]) {
//                swap(nums[i++], nums[++left]);
//            }
//            else if (key < nums[i]) {
//                swap(nums[i], nums[--right]);
//            }
//            else {
//                i++;
//            }
//        }
//        int c = r - right + 1;
//        int b = right - left - 1;
//        if (c >= k) {
//            return qsort(nums, right, r, k);
//        }
//        else if (b + c >= k) {
//            return key;
//        }
//        else {
//            return qsort(nums, l, left, k - b - c);
//        }
//    }
//
//    int Grand(vector<int>& nums, int l, int r) {
//        int x = rand();
//        return nums[x % (r - l + 1) + l];
//    }
//};


https://leetcode.cn/problems/sort-an-array/description/
//class Solution {
//public:
//    vector<int> sortArray(vector<int>& nums) {
//        srand(time(nullptr));
//        qsort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//
//    void qsort(vector<int>& nums, int l, int r) {
//
//        if (l > r) {
//            return;
//        }
//        int key = GetRandom(nums, l, r);
//        int left = l - 1, i = l, right = r + 1;
//        while (i < right) {
//            if (nums[i] < key) {
//                swap(nums[i++], nums[++left]);
//            }
//            else if (nums[i] > key) {
//                swap(nums[i], nums[--right]);
//            }
//            else {
//                i++;
//            }
//        }
//        qsort(nums, l, left);
//        qsort(nums, right, r);
//    }
//
//    int GetRandom(vector<int>& nums, int l, int r) {
//        int x = rand();
//        return nums[x % (r - l + 1) + l];
//    }
//};
